﻿package binarytree;

import java.util.Stack;

import common.*;

public class 二叉树的顺序便利 {

	/**
	 * 二叉树的先序遍历的递归实现
	 * 
	 * @param root
	 */
	public void preOrderRecur(BTNode root) {
		if (root == null) {
			return;
		}
		System.out.print(root.value + " ");
		preOrderRecur(root.left);
		preOrderRecur(root.right);
	}

	/**
	 * 二叉树的中序遍历的递归实现
	 * 
	 * @param root
	 */
	public void inOrderRecur(BTNode root) {
		if (root == null) {
			return;
		}
		preOrderRecur(root.left);
		System.out.print(root.value + " ");
		preOrderRecur(root.right);
	}

	/**
	 * 二叉树的后序遍历的递归实现
	 * 
	 * @param root
	 */
	public void posOrderRecur(BTNode root) {
		if (root == null) {
			return;
		}
		System.out.print(root.value + " ");
		preOrderRecur(root.right);
		preOrderRecur(root.left);
	}

	/**
	 * 用递归方法能解决的问题都能用非递归的方法实现。因为递归方法无非就是利用函数栈来保存信息，如果用自己申请的数据结构栈来替代函数栈，
	 * 也可以实现相同的功能。
	 */

	public void preOrderUnRecur(BTNode root) {
		if (root == null) {
			return;
		}
		Stack<BTNode> stack = new Stack<BTNode>();
		stack.push(root);
		while (!stack.isEmpty()) {
			root = stack.pop();
			System.out.print(root.value + " ");
			// 由于栈是先进后出的，因此应该先让right进入栈中，left再进入栈中
			if (root.right != null) {
				stack.push(root.right);
			}
			if (root.left != null) {
				stack.push(root.left);
			}

		}
	}

	public void inOrderUnRecur(BTNode root) {
		System.out.println("in-order:");
		if (root != null) {
			// 用一个栈来存放所有需要入栈的节点
			Stack<BTNode> stack = new Stack<>();
			while (!stack.isEmpty() || root != null) {
				if (root != null) {
					stack.push(root);
					root = root.left;
				} else {
					root = stack.pop();
					System.out.print(root.value + " ");
					root = root.right;
				}
			}
		}
	}

	public static void posOrderUnRecur1(BTNode root) {
		if (root != null) {
			Stack<BTNode> stack = new Stack<>();
			stack.push(root);
			BTNode c = null;// c为当前栈顶的元素
			while (!stack.isEmpty()) {
				c = stack.peek();
				if (c.left != null && root != c.left && root != c.right) {
					stack.push(c.left);
				} else if (c.right != null && root != c.right) {
					stack.push(c.right);
				} else {
					System.out.print(stack.pop().value + " ");
					root = c;
				}
			}
		}
	}

	public static void posOrderUnRecur2(BTNode root) {
		System.out.println("pos-order:");
		if (root != null) {
			Stack<BTNode> stack1 = new Stack<BTNode>();
			Stack<BTNode> stack2 = new Stack<BTNode>();
			stack1.push(root);
			while (!stack1.isEmpty()) {
				root = stack1.pop();
				stack2.push(root);
				if (root.left != null) {
					stack1.push(root.left);
				}
				if (root.right != null) {
					stack1.push(root.right);
				}
			}
			while (!stack2.isEmpty()) {
				System.out.println(stack2.pop().value + " ");
			}
		}
		System.out.println();
	}
}
